home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d12 / bob13.arc / BOBMEM.C < prev    next >
Encoding:
C/C++ Source or Header  |  1991-10-02  |  13.5 KB  |  571 lines
  1. /* bobmem.c - memory manager */
  2. /*
  3.     Copyright (c) 1991, by David Michael Betz
  4.     All rights reserved
  5. */
  6.  
  7. #include <setjmp.h>
  8. #include "bob.h"
  9.  
  10. /* allocation unit */
  11. typedef char *AUNIT;
  12. #define ALLOCSIZE(x)    (((x) + sizeof(AUNIT) - 1) / sizeof(AUNIT))
  13.  
  14. /* block flags */
  15. #define MARK    1
  16.  
  17. /* size of each type of memory segment */
  18. #define VSSIZE    10000    /* number of LVAL's per vector segment */
  19. #define VCOMPARE(f,s,t)    ((f) + (s) <= (t))
  20.  
  21. /* macros to compute the size of a segment */
  22. #define vsegsize(n) (sizeof(VSEGMENT)+((n)-1)*sizeof(char *))
  23.  
  24. /* macro to convert a byte size to a word size */
  25. #define btow_size(n)    (((n) + sizeof(char *) - 1) / sizeof(char *))
  26.  
  27. /* vector segment structure */
  28. typedef struct vsegment {
  29.     struct vsegment *vs_next;    /* next vector segment */
  30.     AUNIT *vs_free;        /* next free location in this segment */
  31.     AUNIT *vs_top;        /* top of segment (plus one) */
  32.     AUNIT vs_data[1];        /* segment data */
  33. } VSEGMENT;
  34.  
  35. /* global variables */
  36. VALUE symbols;    /* the symbol table */
  37. VALUE classes;    /* the class table */
  38. VALUE nil;    /* the nil value */
  39.  
  40. /* vector (and string) space */
  41. static VSEGMENT *vsegments=NULL;/* list of vector segments */
  42. static VSEGMENT *vscurrent=NULL;/* current vector segment */
  43. static AUNIT *vfree=NULL;    /* next free location in current segment */
  44. static AUNIT *vtop=NULL;    /* top of current segment */
  45.  
  46. /* external variables */
  47. extern jmp_buf error_trap;    /* the error trap target */
  48. extern VECTOR *code;        /* currently executing code vector */
  49.  
  50. /* forward declarations */
  51. void mark();
  52. static HDR *allocmemory();
  53. static void gc(),markclass(),markdictionary(),markentry(),markobject();
  54. static void markvector(),compact(),compact_vector();
  55. static DICT_ENTRY *newentry();
  56.  
  57. /* initialize - initialize the virtual machine */
  58. int initialize(smax,cmax)
  59.   int smax,cmax;
  60. {
  61.     int obj_class(),cls_new();
  62.     char *calloc();
  63.     
  64.     /* setup an error trap handler */
  65.     if (setjmp(error_trap) != 0)
  66.     return (FALSE);
  67.  
  68.     /* allocate the stack */
  69.     if ((stkbase = (VALUE *)calloc(1,smax * sizeof(VALUE))) == NULL)
  70.     return (FALSE);
  71.     stktop = sp = stkbase + smax;
  72.     code = NULL;
  73.  
  74.     /* initialize the memory manager */
  75.     vsegments = vscurrent = NULL;
  76.     vfree = vtop = NULL;
  77.     if (!vexpand(VSSIZE))
  78.     return (FALSE);
  79.  
  80.     /* initialize the compiler */
  81.     if (!init_compiler(cmax))
  82.     return (FALSE);
  83.  
  84.     /* create the symbol and class tables */
  85.     set_nil(&nil);
  86.     set_dictionary(&symbols,newdictionary(&nil));
  87.     set_dictionary(&classes,newdictionary(&nil));
  88.  
  89.     /* enter the built-in functions */
  90.     init_functions();
  91.     return (TRUE);
  92. }
  93.  
  94. /* addentry - add an entry to a dictionary */
  95. DICT_ENTRY *addentry(dict,key,type)
  96.   VALUE *dict; char *key; int type;
  97. {
  98.     DICT_ENTRY *entry;
  99.     if ((entry = findentry(dict,key)) == NULL) {
  100.     check(1);
  101.     push_var(newentry(dict,key,type));
  102.     sp->v.v_var->de_next = *digetcontents(dict);
  103.     dict->v.v_dictionary->di_contents = *sp;
  104.     entry = deaddr(sp++);
  105.     }
  106.     return (entry);
  107. }
  108.  
  109. /* findentry - find an entry in a dictionary */
  110. DICT_ENTRY *findentry(dict,key)
  111.   VALUE *dict; char *key;
  112. {
  113.     DICT_ENTRY *entry;
  114.     for (entry = digetcontents(dict)->v.v_var;
  115.      entry != NULL;
  116.      entry = entry->de_next.v.v_var)
  117.     if (strncmp(key,
  118.             strgetdata(&entry->de_key),
  119.             strgetsize(&entry->de_key)) == 0)
  120.         return (entry);
  121.     return (NULL);
  122. }
  123.  
  124. /* makestring - make an initialized string from a C-style string */
  125. STRING *makestring(str)
  126.   char *str;
  127. {
  128.     STRING *val;
  129.     int len;
  130.     len = strlen(str);
  131.     val = newstring(len);
  132.     strncpy(val->str_data,str,len);
  133.     return (val);
  134. }
  135.  
  136. /* getcstring - get a C-style version of a string */
  137. char *getcstring(buf,max,str)
  138.   char *buf; int max; VALUE *str;
  139. {
  140.     int len;
  141.     if ((len = strgetsize(str)) >= max)
  142.     len = max - 1;
  143.     strncpy(buf,strgetdata(str),len);
  144.     buf[len] = '\0';
  145.     return (buf);
  146. }
  147.  
  148. /* newstring - allocate a new string object */
  149. STRING *newstring(n)
  150.   int n;
  151. {
  152.     STRING *val;
  153.     int size;
  154.     char *p;
  155.     size = sizeof(STRING) + n - 1;
  156.     val = (STRING *)allocmemory(DT_STRING,size);
  157.     val->str_size = n;
  158.     for (p = val->str_data; --n >= 0; )
  159.     *p++ = '\0';
  160.     return (val);
  161. }
  162.  
  163. /* newobject - allocate a new object */
  164. OBJECT *newobject(class)
  165.   VALUE *class;
  166. {
  167.     OBJECT *val;
  168.     int size,n;
  169.     VALUE *p;
  170.     n = clgetsize(class);
  171.     size = sizeof(OBJECT) + (n - 1) * sizeof(VALUE);
  172.     val = (OBJECT *)allocmemory(DT_OBJECT,size);
  173.     val->obj_class = *class;
  174.     for (p = val->obj_members; --n >= 0; ++p)
  175.     p->v_type = DT_NIL;
  176.     return (val);
  177. }
  178.  
  179. /* newvector - allocate a new vector */
  180. VECTOR *newvector(n)
  181.   int n;
  182. {
  183.     VECTOR *val;
  184.     VALUE *p;
  185.     int size;
  186.     size = sizeof(VECTOR) + (n - 1) * sizeof(VALUE);
  187.     val = (VECTOR *)allocmemory(DT_VECTOR,size);
  188.     val->vec_size = n;
  189.     for (p = val->vec_data; --n >= 0; ++p)
  190.     p->v_type = DT_NIL;
  191.     return (val);
  192. }
  193.  
  194. /* newclass - create a new class */
  195. CLASS *newclass(name,base)
  196.   char *name; VALUE *base;
  197. {
  198.     /* allocate the memory for the new class */
  199.     check(1);
  200.     push_class((CLASS *)allocmemory(DT_CLASS,sizeof(CLASS)));
  201.     set_nil(&sp->v.v_class->cl_name);
  202.     set_nil(&sp->v.v_class->cl_members);
  203.     set_nil(&sp->v.v_class->cl_functions);
  204.  
  205.     /* initialize */
  206.     sp->v.v_class->cl_base = *base;
  207.     set_string(&sp->v.v_class->cl_name,makestring(name));
  208.     set_dictionary(&sp->v.v_class->cl_members,newdictionary(sp));
  209.     set_dictionary(&sp->v.v_class->cl_functions,newdictionary(sp));
  210.     sp->v.v_class->cl_size = 0;
  211.  
  212.     /* return the new class */
  213.     return (claddr(sp++));
  214. }
  215.  
  216. /* newdictionary - create a new dictionary */
  217. DICTIONARY *newdictionary(class)
  218.   VALUE *class;
  219. {
  220.     DICTIONARY *dict;
  221.     dict = (DICTIONARY *)allocmemory(DT_DICTIONARY,sizeof(DICTIONARY));
  222.     dict->di_class = *class;
  223.     set_nil(&dict->di_contents);
  224.     return (dict);
  225. }
  226.  
  227. /* newentry - allocate a new dictionary entry */
  228. static DICT_ENTRY *newentry(dict,key,type)
  229.   VALUE *dict; char *key; int type;
  230. {
  231.     check(1);
  232.     push_var((DICT_ENTRY *)allocmemory(DT_VAR,sizeof(DICT_ENTRY)));
  233.     sp->v.v_var->de_dictionary = *dict;
  234.     sp->v.v_var->de_type = type;
  235.     set_nil(&sp->v.v_var->de_key);
  236.     set_nil(&sp->v.v_var->de_value);
  237.     set_nil(&sp->v.v_var->de_next);
  238.     set_string(&sp->v.v_var->de_key,makestring(key));
  239.     return (deaddr(sp++));
  240. }
  241.  
  242. /* allocmemory - allocate a block of memory */
  243. static HDR *allocmemory(type,size)
  244.   int type,size;
  245. {
  246.     HDR *val;
  247.  
  248.     /* make sure there's enough space */
  249.     size = ALLOCSIZE(size);
  250.     if (!VCOMPARE(vfree,size,vtop)
  251.     &&  !checkvmemory(size)
  252.     &&  !findvmemory(size))
  253.     error("Insufficient memory");
  254.  
  255.     /* allocate the next available block */
  256.     val = (HDR *)vfree;
  257.     vfree += size;
  258.     
  259.     /* return the new block of memory */
  260.     val->hdr_type = type;
  261.     val->hdr_flags = 0;
  262.     val->hdr_chain = NULL;
  263.     return (val);
  264. }
  265.  
  266. /* findvmemory - find vector memory */
  267. static int findvmemory(size)
  268.   int size;
  269. {
  270.     /* try garbage collecting */
  271.     gc();
  272.  
  273.     /* check to see if we found enough memory */
  274.     if (VCOMPARE(vfree,size,vtop) || checkvmemory(size))
  275.     return (TRUE);
  276.  
  277.     /* expand vector space */
  278.     return (makevmemory(size));
  279. }
  280.  
  281. /* checkvmemory - check for vector memory (used by 'xsimage.c') */
  282. static int checkvmemory(size)
  283.   int size;
  284. {
  285.     VSEGMENT *vseg;
  286.     for (vseg = vsegments; vseg != NULL; vseg = vseg->vs_next)
  287.     if (vseg != vscurrent && VCOMPARE(vseg->vs_free,size,vseg->vs_top)) {
  288.         if (vscurrent != NULL)
  289.         vscurrent->vs_free = vfree;
  290.         vfree = vseg->vs_free;
  291.         vtop = vseg->vs_top;
  292.         vscurrent = vseg;
  293.         return (TRUE);
  294.     }    
  295.     return (FALSE);
  296. }
  297.     
  298. /* makevmemory - make vector memory (used by 'xsimage.c') */
  299. static int makevmemory(size)
  300.   int size;
  301. {
  302.     return (vexpand(size < VSSIZE ? VSSIZE : size));
  303. }
  304.  
  305. /* vexpand - expand vector space */
  306. static int vexpand(size)
  307.   int size;
  308. {
  309.     VSEGMENT *newvsegment(),*vseg;
  310.  
  311.     /* allocate the new segment */
  312.     if ((vseg = newvsegment(size)) != NULL) {
  313.  
  314.     /* initialize the new segment and make it current */
  315.     if (vscurrent != NULL)
  316.         vscurrent->vs_free = vfree;
  317.     vfree = vseg->vs_free;
  318.     vtop = vseg->vs_top;
  319.     vscurrent = vseg;
  320.     }
  321.     return (vseg != NULL);
  322. }
  323.  
  324. /* newvsegment - create a new vector segment */
  325. static VSEGMENT *newvsegment(n)
  326.   unsigned int n;
  327. {
  328.     char *calloc();
  329.     VSEGMENT *newseg;
  330.  
  331.     /* allocate the new segment */
  332.     if ((newseg = (VSEGMENT *)calloc(1,vsegsize(n))) == NULL)
  333.     return (NULL);
  334.  
  335.     /* initialize the new segment */
  336.     newseg->vs_free = newseg->vs_data;
  337.     newseg->vs_top = newseg->vs_free + n;
  338.     newseg->vs_next = vsegments;
  339.     vsegments = newseg;
  340.  
  341.     /* return the new segment */
  342.     return (newseg);
  343. }
  344.  
  345. /* gc - garbage collect */
  346. static void gc()
  347. {
  348.     extern unsigned char *cbase,*pc;
  349.     VALUE codeval,*p;
  350.     LITERAL *lit;
  351.     int pcoff;
  352.  
  353.     /* protect the current bytecode vector */
  354.     if (code) {
  355.     set_bytecode(&codeval,code);
  356.     pcoff = pc - cbase;
  357.     mark(&codeval);
  358.     }
  359.  
  360.     /* mark all reachable values */
  361.     mark(&symbols);
  362.     mark(&classes);
  363.  
  364.     /* mark the stack */
  365.     for (p = sp; p < stktop; )
  366.     mark(p++);
  367.  
  368.     /* mark compiler variables */
  369.     mark_compiler();
  370.  
  371.     /* compact all active blocks */
  372.     compact();
  373.  
  374.     /* reload the interpreter's registers */
  375.     if (code) {
  376.     code = codeval.v.v_vector;
  377.     cbase = code->vec_data[0].v.v_string->str_data;
  378.     pc = cbase + pcoff;
  379.     }
  380. }
  381.  
  382. /* mark - mark all accessible nodes */
  383. void mark(val)
  384.   VALUE *val;
  385. {
  386.     HDR *hdr;
  387.     switch (val->v_type) {
  388.     case DT_CLASS:
  389.     case DT_OBJECT:
  390.     case DT_VECTOR:
  391.     case DT_BYTECODE:
  392.     case DT_STRING:
  393.     case DT_DICTIONARY:
  394.     case DT_VAR:
  395.     hdr = val->v.v_hdr;
  396.     val->v.v_chain = hdr->hdr_chain;
  397.     hdr->hdr_chain = val;
  398.     if ((hdr->hdr_flags & MARK) == 0) {
  399.         hdr->hdr_flags |= MARK;
  400.         switch (hdr->hdr_type) {
  401.         case DT_CLASS:
  402.         markclass((CLASS *)hdr);
  403.         break;
  404.         case DT_OBJECT:
  405.         markobject((OBJECT *)hdr);
  406.         break;
  407.         case DT_VECTOR:
  408.         markvector((VECTOR *)hdr);
  409.         break;
  410.         case DT_DICTIONARY:
  411.         markdictionary((DICTIONARY *)hdr);
  412.         break;
  413.         case DT_VAR:
  414.         markentry((DICT_ENTRY *)hdr);
  415.         break;
  416.         }
  417.     }
  418.     break;
  419.     }
  420. }
  421.  
  422. /* markclass - mark a class */
  423. static void markclass(class)
  424.   CLASS *class;
  425. {
  426.     mark(&class->cl_name);
  427.     mark(&class->cl_base);
  428.     mark(&class->cl_members);
  429.     mark(&class->cl_functions);
  430. }
  431.  
  432. /* markdictionary - mark a dictionary */
  433. static void markdictionary(dict)
  434.   DICTIONARY *dict;
  435. {
  436.     VALUE *next,*val;
  437.     mark(&dict->di_class);
  438.     for (val = &dict->di_contents;
  439.      !isnil(val);
  440.      val = next) {
  441.     next = degetnext(val);
  442.     mark(val);
  443.     }
  444. }
  445.  
  446. /* markentry - mark a dictionary entry */
  447. static void markentry(entry)
  448.   DICT_ENTRY *entry;
  449. {
  450.     mark(&entry->de_dictionary);
  451.     mark(&entry->de_key);
  452.     mark(&entry->de_value);
  453. }
  454.  
  455. /* markobject - mark an object */
  456. static void markobject(obj)
  457.   OBJECT *obj;
  458. {
  459.     VALUE *p;
  460.     int n;
  461.     p = obj->obj_members;
  462.     n = clgetsize(&obj->obj_class);
  463.     while (--n >= 0)
  464.     mark(p++);
  465. }
  466.  
  467. /* markvector - mark a vector */
  468. static void markvector(vect)
  469.   VECTOR *vect;
  470. {
  471.     VALUE *p;
  472.     int n;
  473.     p = vect->vec_data;
  474.     n = vect->vec_size;
  475.     while (--n >= 0)
  476.     mark(p++);
  477. }
  478.  
  479. /* compact - compact vector space */
  480. static void compact()
  481. {
  482.     VSEGMENT *vseg;
  483.  
  484.     /* store the current segment information */
  485.     if (vscurrent)
  486.     vscurrent->vs_free = vfree;
  487.  
  488.     /* compact each vector segment */
  489.     for (vseg = vsegments; vseg != NULL; vseg = vseg->vs_next)
  490.     compact_vector(vseg);
  491.  
  492.     /* make the first vector segment current */
  493.     if ((vscurrent = vsegments) != NULL) {
  494.     vfree = vscurrent->vs_free;
  495.     vtop = vscurrent->vs_top;
  496.     }
  497. }
  498.  
  499. /* getblocksize - get the size of a block */
  500. static int getblocksize(hdr)
  501.   HDR *hdr;
  502. {
  503.     switch (hdr->hdr_type) {
  504.     case DT_CLASS:
  505.     return (ALLOCSIZE(sizeof(CLASS)));
  506.     case DT_OBJECT:
  507.     return (ALLOCSIZE(sizeof(OBJECT)
  508.          +  (clgetsize(&((OBJECT *)hdr)->obj_class) - 1) * sizeof(VALUE)));
  509.     case DT_VECTOR:
  510.     return (ALLOCSIZE(sizeof(VECTOR)
  511.          +  (((VECTOR *)hdr)->vec_size - 1) * sizeof(VALUE)));
  512.     case DT_STRING:
  513.     return (ALLOCSIZE(sizeof(STRING)
  514.          +  ((STRING *)hdr)->str_size - 1));
  515.     case DT_DICTIONARY:
  516.     return (ALLOCSIZE(sizeof(DICTIONARY)));
  517.     case DT_VAR:
  518.     return (ALLOCSIZE(sizeof(DICT_ENTRY)));
  519.     }
  520.     error("Bad block type: %d",hdr->hdr_type);
  521.     return (0);
  522. }
  523.  
  524. /* compact_vector - compact a vector segment */
  525. static void compact_vector(vseg)
  526.   VSEGMENT *vseg;
  527. {
  528.     AUNIT *vdata,*vnext,*vfree;
  529.     VALUE *vp,*nextvp;
  530.     int vsize;
  531.     HDR *hdr;
  532.  
  533.     /* update pointers */
  534.     vdata = vnext = vseg->vs_data;
  535.     vfree = vseg->vs_free;
  536.     while (vdata < vfree) {
  537.     hdr = (HDR *)vdata;
  538.     vsize = getblocksize(hdr);
  539.     if (hdr->hdr_flags & MARK) {
  540.         for (vp = hdr->hdr_chain; vp != NULL; vp = nextvp) {
  541.         nextvp = vp->v.v_chain;
  542.         vp->v.v_hdr = (HDR *)vnext;
  543.         }
  544.         hdr->hdr_chain = NULL;
  545.         vnext += vsize;
  546.     }
  547.     vdata += vsize;
  548.     }
  549.  
  550.     /* compact free space */
  551.     vdata = vnext = vseg->vs_data;
  552.     vfree = vseg->vs_free;
  553.     while (vdata < vfree) {
  554.     hdr = (HDR *)vdata;
  555.     vsize = getblocksize(hdr);
  556.     if (hdr->hdr_flags & MARK) {
  557.         hdr->hdr_flags &= ~MARK;
  558.         if (vdata == vnext) {
  559.         vdata += vsize;
  560.         vnext += vsize;
  561.         }
  562.         else
  563.         while (--vsize >= 0)
  564.             *vnext++ = *vdata++;
  565.     }
  566.     else
  567.         vdata += vsize;
  568.     }
  569.     vseg->vs_free = vnext;
  570. }
  571.